import java.util.HashMap;
//丢失的数字
//https://leetcode.cn/problems/missing-number/submissions/604840629/
public class Test {
    public static void main(String[] args) {
        //
    }
}

class Solution3 {
    public int missingNumber(int[] nums) {
        //方法三：位运算（抑或运算）
        int n = nums.length;//需要明确：nums中，最大的数是n

        int resuslt = 0;
        for (int i = 0; i < n; i++) {

            resuslt ^= ((i + 1) ^ nums[i]);
        }
        return resuslt;
    }
}
class Solution2 {
    public int missingNumber(int[] nums) {
        //方法二：求和（高斯balabala）
        int sum_nums = 0;//所给数组的和
        int sum = 0;//不缺元素的和
        for(int n : nums){
            sum_nums += n;
        }
        /*//可以用这种方式求sum
        for(int i = 0 ; i <= nums.length ; i++){
            sum += i;
        }*/
        //也可以用这种方式求sum
        //       直接利用数学等差数列公式，节省空间开销
        int n = nums.length;
        sum = (1+n)*n/2;//注意：这里公式，“首项”——1，“项数”——n
        return sum - sum_nums;

    }
}
class Solution1 {
    public int missingNumber(int[] nums) {

        //方法一：哈希表
        //创建一个相同规模的哈希表
        HashMap hashMap = new HashMap<Integer, Boolean>();
        boolean ret = false;
        for(int i = 0;i < nums.length;i++){
            hashMap.put(i,true);
        }
        for(int i = 0; i< nums.length;i++){
            //↓这里，为啥报错呢？？？
            //ret = hashMap.getOrDefault(nums[i],(Boolean)false);//——Java的基础语法知识~~~
            ret = (boolean) hashMap.getOrDefault(nums[i],false);
            if(!ret){
                break;
            }
        }
        return ret;
    }
}
